package offer.easy;

public class SubArray {

    //最大子串和
    public static int maxSumOfSubArray(int[] array) {
        int max = array[0];
        int temp = array[0];
        int[] sum = new int[array.length];
        sum[0] = array[0];
        for (int i = 1; i < array.length; i++) {
            //sum[i] = array[i] + sum[i-1]>0?sum[i-1]:0;
            temp = sum[i-1]>0?sum[i-1]:0;
            sum[i] = array[i] + temp;
        }
        for (int i = 0; i < sum.length; i++) {
            if (max < sum[i]) {
                max = sum[i];
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int array[] = {-2,-8,-1,-5,-9};
        int[] sum = new int[array.length];
        sum[0] = array[0];
        System.out.println(array[1] + sum[0]>0?sum[0]:0);
        int max = maxSumOfSubArray(array);
        System.out.println("The MAX:"+max);
    }
}
